package pl.pw.gis.gc_sa.algo;

import java.util.ArrayList;
import java.util.HashMap;

import pl.pw.gis.gc_sa.data.Graph;
import pl.pw.gis.gc_sa.data.Vertex;
import pl.pw.gis.gc_sa.data.VertexChange;

/**
 * Klasa rozwiazujaca problem kolorowania wierzcholkow metoda symulowanego
 * wyzarzania (w osobnym watku), kazde nowe rozwiazanie dopuszczalne
 * 
 * @author Maciek
 * 
 */
public class SimulatedAnnealing extends GcSolver {
    public final static int COST_ARTICLE = 0;
    public final static int COST_COLOR_COUNT = COST_ARTICLE + 1;

    public final static float TEMP_MIN_DEF = 1.0E-4f;
    public final static float TEMP_START_DEF = 100;
    public final static float TEMP_DIFF_DEF = 0.9f;
    public final static boolean GENERATE_LEGAL_DEF = false;
    public final static boolean USE_WORSE_DEF = true;
    public final static boolean INIT_LEGAL_DEF = true;
    public final static int COST_METHOD_DEF = COST_ARTICLE;

    /** Temperatura minimalna */
    protected float mTempMin = TEMP_MIN_DEF;
    /** Temperatura poczatkowa */
    protected float mTempStart = TEMP_START_DEF;
    /** Zmiana temperatury w kolejnych krokach - schladzanie geometryczne */
    protected float mTempDiff = TEMP_DIFF_DEF;
    /** czy nowe wygenerowane rozwiazania maja byc dopuszczalne */
    protected boolean mGenerateLegal = GENERATE_LEGAL_DEF;
    /** czy generowac gorsze rozwiazania (wiecej klas kolorow niz bylo) */
    protected boolean mUseWorse = USE_WORSE_DEF;
    /** czy zainicjowac legalnie czy jako wszystkie wierzcholki w jednym kolorze */
    protected boolean mInitLegal = INIT_LEGAL_DEF;
    /** jaka metoda wyliczac koszt kolorowania */
    protected int mCostMethod = COST_METHOD_DEF;

    protected int[] mCurrentSolution;
    protected int[] mPrevSolution;

    protected float mTemp;
    protected long mStartTime;

    /**
     * Domyslny konstruktor przyjmujacy jako parametr jedynie niepokolorowany
     * graf. Wszystkie parametry algorytmu przyjmuja wartosci domyslne
     * 
     * @param graph
     *            niepokolorowany graf.
     */
    public SimulatedAnnealing(Graph graph) {
        super(graph);
        mCurrentSolution = new int[graph.getVerticesCount()];
        mPrevSolution = new int[graph.getVerticesCount()];
    }

    /**
     * Konstruktor przyjmujacy poza niepokolorowanym grafem, takze parametry
     * dotyczace inicjalizacji kolorowania oraz sposobu generowania nowych
     * rozwiazan
     * 
     * @param graph
     *            niepokolorowany graf wejsciowy
     * @param generateLegal
     *            czy nowe wygenerowane rozwiazania maja byc dopuszczalne
     * @param useWorse
     *            czy generowac gorsze rozwiazania (wiecej klas kolorow niz
     *            bylo)
     * @param initLegal
     *            czy zainicjowac graf legalnym kolorowaniem. W przeciwnym
     *            wypadku koloruje jednym kolorem
     */
    public SimulatedAnnealing(Graph graph, boolean generateLegal,
            boolean useWorse, boolean initLegal, int costMethod) {
        this(graph);
        mGenerateLegal = generateLegal;
        mUseWorse = useWorse;
        mInitLegal = initLegal;
        mCostMethod = costMethod;
    }

    /**
     * Konstruktor przyjmujacy poza niepokolorowanym grafem, takze parametry
     * dotyczace temperatury oraz ograniczenia liczby iteracji
     * 
     * @param graph
     *            niepokolorowany graf wejsciowy
     * @param tempMin
     *            minimalna temperatura
     * @param tempStart
     *            poczatkowa temperatura
     * @param tempDiff
     *            roznica temperatury (schladzanie geometryczne:
     *            temp=temp*tempDiff
     * @param iterMax
     *            liczba iteracji w wewnetrznej petli (przy tej samej
     *            temperaturze)
     */
    public SimulatedAnnealing(Graph graph, float tempMin, float tempStart,
            float tempDiff, int iterMax) {
        this(graph);
        mTempMin = tempMin;
        mTempStart = tempStart;
        mTempDiff = tempDiff;
        mNoIterMax = iterMax;
    }

    /**
     * Kontruktor pozwalajacy ustawic wszystkie parametry algorytmu
     * 
     * @param graph
     *            niepokolorowany graf wejsciowy
     * @param generateLegal
     *            czy nowe wygenerowane rozwiazania maja byc legalne
     * @param useWorse
     *            czy generowac gorsze rozwiazania (z wieksza liczba kolorow)
     * @param initLegal
     *            czy inicjowac legalnym kolorowaniem. W przeciwnym wypadku
     *            koloruje jednym kolorem
     * @param tempMin
     *            minimalna temperatura
     * @param tempStart
     *            poczatkowa temperatura
     * @param tempDiff
     *            roznica temperatury (schladzanie geometryczne:
     *            temp=temp*tempDiff
     * @param iterMax
     *            liczba iteracji w wewnetrznej petli (przy tej samej
     *            temperaturze)
     */
    public SimulatedAnnealing(Graph graph, boolean generateLegal,
            boolean useWorse, boolean initLegal, float tempMin,
            float tempStart, float tempDiff, int iterMax, int costMethod,
            int noChangeIterMax) {
        this(graph, tempMin, tempStart, tempDiff, iterMax);
        mGenerateLegal = generateLegal;
        mUseWorse = useWorse;
        mInitLegal = initLegal;
        mCostMethod = costMethod;
        mNoChangeIterMax = noChangeIterMax;
    }

    /** Metoda rozwiazujaca */
    public void doRun() {

        if (mInitLegal)
            initBestSolutionLegal();
        else
            initBestSolutionAllSame();

        adjustNoIterMaxValue();

        mCurrentSolution = mBestSolution.clone();
        mPrevSolution = mBestSolution.clone();

        switch (mCostMethod) {

        case COST_COLOR_COUNT:
            mCost = new CostAsColorCount(mGraph, mCurrentSolution);
            break;
        case COST_ARTICLE:
        default:
            mCost = new CostFromArticle(mGraph, mCurrentSolution);
            break;
        }

        mBestCost = mCost.getCurrentCost();
        mTemp = mTempStart;
        mStartTime = System.currentTimeMillis();

        while (mTemp > mTempMin && mNoChangeIter < mNoChangeIterMax) {
            mNoIter = 0;
            mNoChangeIter++;
            while (mNoIter < mNoIterMax) {
                mNoIter++;
                VertexChange change = generateNewSolution(mPrevSolution,
                        mGenerateLegal, mUseWorse);

                if (!change.skipMe()) continue;

                int prevCost = mCost.getCurrentCost();
                int currentCost = mCost.costAfterChange(change);
                int costDiff = currentCost - prevCost;
                mCurrentSolution = mPrevSolution.clone();
                mCurrentSolution[change.getVertexId()] = change.getNewColor();

                /**
                 * Wywolywana w sytuacji, gdy biezace rozwiazanie ma lepszy
                 * koszt od poprzedniego.
                 */
                if ((costDiff <= 0) ||
                /**
                 * Wywolywane w sytuacji, gdy biezace rozwiazanie ma gorszy
                 * koszt od poprzedniego, jednak spelnione jest
                 * prawdopodobienstwo zamiany rozwiania pomimo gorszego kosztu.
                 */
                ((mRandom.nextFloat() < (float) Math.exp(-costDiff / mTemp)))) {
                    mCost.applyChange(change, currentCost);
                    mPrevSolution = mCurrentSolution.clone();
                    // Aktualizujemy najlepsze rozwiazanie
                    if (mCost.getCurrentCost() < mBestCost) {
                        mNoChangeIter = 0;
                        mBestCost = mCost.getCurrentCost();
                        mBestSolution = mCurrentSolution.clone();
                    }
                }
            }
            mTemp *= mTempDiff; // nowa wartosc temperatury
        }
        if (mNoChangeIter == mNoChangeIterMax)
            System.out.println("SA: stopped because of lack of improvement");

        // konczymy
        mComputingTime = System.currentTimeMillis() - mStartTime;
        mDone = true;
    }

    /**
     * Szukanie nowego rozwiazanie wg funkcji z artykulu
     * 
     * @param tab
     *            tablica aktualnego kolorowania
     * @param legal
     *            czy rozwiazanie ma byc legalne (tzn nie powodujace kolizji
     *            kolorow)
     * @param useWorse
     *            czy generowac gorsze rozwiazania (wiecej klas kolorow niz
     *            bylo)
     * @return VertexChange ktory nie jest "valid" tylko jesli zostal 1 kolor i
     *         wylosowano dodanie nowej klasy, kazda inna zmiana jest dozwolona
     */
    protected VertexChange generateNewSolution(int[] tab, boolean legal,
            boolean useWorse) {

        // Unikamy zapetlenia dalej
        if (mGraph.getVerticesCount() == 0 || mGraph.getEdgesCount() == 0)
            return new VertexChange(0, 0, 0, false);

        // lista klas wraz z przynalezacymi do nimi id wierzcholkow
        HashMap<Integer, ArrayList<Integer>> colors = new HashMap<Integer, ArrayList<Integer>>();
        for (int i = 0; i < tab.length; i++) {
            if (!colors.containsKey(tab[i]))
                colors.put(tab[i], new ArrayList<Integer>());
            colors.get(tab[i]).add(i);
        }

        int cOld = tab[mRandom.nextInt(tab.length)];
        ArrayList<Integer> vInCold = colors.get(cOld);
        int v = vInCold.get(mRandom.nextInt(vInCold.size()));
        int i;
        if (useWorse)
            i = mRandom.nextInt(colors.size() + 1);
        else
            i = mRandom.nextInt(colors.size());

        // Dodajemy nowy kolor jesli wylosowalismy n + 1
        if (i == colors.size() && colors.size() != mGraph.getVerticesCount()) {
            // Wybieramy taki ktorego nie ma
            int newColor = mRandom.nextInt(mGraph.getVerticesCount());
            while (colors.containsKey(newColor))
                newColor = mRandom.nextInt(mGraph.getVerticesCount());

            return new VertexChange(v, tab[v], newColor, true);
        }
        // jesli 1 wierzcholek to nic nie zmieniamy bo nie mamy z czym
        else if (colors.size() == 1) {
            return new VertexChange(0, 0, 0, false);
        }
        // inaczej przypisujemy wierzcholkowi v z klasy cOld nowy kolor
        else {
            return changeColor(tab, v, legal);
        }
    }

    /**
     * Zmienia kolor zadanego wierzcholka v na nowy, losowy kolor z juz
     * istniejacej klasy kolorow
     * 
     * @param tab
     *            biezace kolorowanie
     * @param v
     *            indeks modyfikowanego wierzcholka
     * @param legal
     *            czy kolorowanie musi byc legalne (dopuszczalne)
     * @return obiekt VertexChange zawierajacy informacje o starym i nowym
     *         kolorze, indeks wierzcholka oraz to, czy kolorwanie jest poprawne
     */
    protected VertexChange changeColor(int[] tab, int v, boolean legal) {
        int oldColor = tab[v];
        int newColor = tab[mRandom.nextInt(tab.length)];
        while (newColor == oldColor)
            newColor = tab[mRandom.nextInt(tab.length)];

        boolean valid = true;
        if (legal) {
            // sprawdzamy czy po zmianie wszystkie sasiednie wierzcholki beda
            // mialy
            // rozne kolory
            for (Vertex neigh : mGraph.getAdjacent(v)) {
                if (tab[neigh.getId()] == newColor) {
                    valid = false;
                    break;
                }
            }
        }

        return new VertexChange(v, oldColor, newColor, valid);
    }

    @Override
    public String getMethodName() {
        return "Simulated Annealing";
    }

    @Override
    public String getMethodParameters() {
        String spaceSign = " ";
        return "mGenerateLegal=" + mGenerateLegal + spaceSign + "mUseWorse="
                + mUseWorse + spaceSign + "mInitLegal=" + mInitLegal
                + spaceSign + "mTempMin=" + mTempMin + spaceSign
                + "mTempStart=" + mTempStart + spaceSign + "mTempDiff="
                + mTempDiff + spaceSign + "mNoChangeIterMax="
                + mNoChangeIterMax + spaceSign + "mNoIterMax=" + mNoIterMax;

    }

    @Override
    public String getMethodOutcome() {
        String spaceSign = " ";
        return "MinColorCount=" + getMinColorCount() + spaceSign + "IsValid="
                + isSolutionValid() + spaceSign + "IsDone=" + isDone()
                + spaceSign + "UseWorse=" + mUseWorse + spaceSign + "Time="
                + (isDone() ? mComputingTime : "NotFinished");
    }
}
